package search;

import java.util.Arrays;

/**
 * 二分查找算法
 * @Auther Jun jie Yi
 * @Date 16:26 2021/7/12
 */
public class BinarySearch {

    static int count = 0;//记录查找次数
    static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i + 1;
        }
        //int i = BinarySearch.binarySearch(arr, 6);
        //int i = BinarySearch.binarySearchRecursion(arr, 0, arr.length - 1,6);
        //int i = BinarySearch.binaryInsertSearch(arr, 45);
        //int i = BinarySearch.binaryInsertSearchRecursion(arr, 0, arr.length - 1, 77);
        //System.out.println(i + " 查找次数：" + count);

        System.out.println(BinarySearch.fibonacciSearch(arr, 45));

    }

    //顺序查找算法
    //二分查找算法(有序)
    public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1; // 注意
        while(left <= right) { // 注意
            count ++;
            int mid = (right + left) / 2;
            if(arr[mid] == key)
                return mid;
            else if (arr[mid] < key)
                left = mid + 1; // 注意
            else if (arr[mid] > key)
                right = mid - 1; // 注意
        }
        return -1;
    }

    //二分查找算法(递归)
    public static int binarySearchRecursion(int[] arr, int left, int right, int key) {
        count ++;
        if(left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if(key > midVal) {
            return binarySearchRecursion(arr, mid + 1, right, key);
        } else if(key < midVal) {
            return binarySearchRecursion(arr, left, mid - 1, key);
        } else {
            return mid;
        }
    }

    //插值查找算法 => 效率最高(推荐)
    public static int binaryInsertSearch(int[] arr, int key) {
        int left = 0;
        int mid;
        int right = arr.length - 1; // 注意
        if(left > right || key < arr[0] || key > arr[arr.length - 1]) {
            return -1;
        }
        while(left <= right) { // 注意
            count ++;
            mid = left + (right - left) * (key - arr[left]) / (arr[right] - arr[left]);
            if(arr[mid] == key)
                return mid;
            else if (arr[mid] < key)
                left = mid + 1; // 注意
            else if (arr[mid] > key)
                right = mid - 1; // 注意
        }
        return -1;
    }

    //插值查找算法(递归)
    public static int binaryInsertSearchRecursion(int[] arr, int left, int right, int key) {
        count ++;
        if(left > right || key < arr[0] || key > arr[arr.length - 1]) {
            return -1;
        }
        //这里要注意顺序如果除数放在前面算出来的数就会是 0 (如果跳跃性特别大的情况下这个算法不一定会比折半)
        int mid = left + (right - left) * (key - arr[left]) / (arr[right] - arr[left]);

        System.out.println(mid);
        int midVal = arr[mid];
        if(key > midVal) {
            return binaryInsertSearchRecursion(arr, mid + 1, right, key);
        } else if(key < midVal) {
            return binaryInsertSearchRecursion(arr, left, mid - 1, key);
        } else {
            return mid;
        }
    }

    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    //斐波那契查找算法(这里也是改变中间结点的 mid 的值，仍然要满足有序数组)
    //F(k) - 1 = (F(k-1)-1) + (F(k-2)-1) + 1
    //mid = low + F(k-1) - 1
    //这里使用非递归的方式的得到
    public static int fibonacciSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int k = 0; //表示斐波那契数值分割的下标
        int mid = 0; //存放 mid 的值
        int f[] = fib(); //获取一个斐波那契数列
        //获取斐波那契分割数值的下标
        while(high > f[k] - 1) {
            k ++;
        }
        //应为f[k]值可能 > arr 的长度，因此我们需要使用Arrays类，构造一个数组，并指向 arr[]
        //不足的部分会用 0 填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        for(int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while循环找到key
        while (low <= high) {
            count ++;//查了多少次
            mid = low + f[k - 1] - 1;//得到mid的下标
            if (key < temp[mid]) {//继续向数组前部分查找（左边）
                high = mid - 1;
                //为什么是k--;
                //说明：
                //1.全部元素=前边元素+后边元素
                //2.f[k] = f[k-1] + f[k-2]
                //因为前面的 f[k-1] 个元素，所以我们可以继续拆分，f[k-1] = f[k-2] + f[k-3]
                //即再f[k-1]的前面继续查找，k--
                k--;
            } else if (key>temp[mid]){//继续向数组后部分查找（右边）
                low = mid + 1;
                //为什么是k-2；
                //说明：
                //1.全部元素=前边元素+后边元素
                //2.f[k] = f[k-1] + f[k-2]
                //3.后面右 f[k-2] 个元素，继续拆分
                //即下次循环 mid = f[k-1-2] - 1。
                k -= 2;
            } else{//找到
                //需要确定，返回哪个值
                if(mid<=high){
                    return mid;
                }else{
                    return high; //处理后面延长的数组
                }
            }
        }
        return -1;
    }
}
